package org.example.Soution003;

import java.util.Arrays;

public class MDDPLongestPalindromeString {
    public static void main(String[] args) {
        MDDPLongestPalindromeString m = new MDDPLongestPalindromeString();
        System.out.println(m.longestPalindrome("bcddcbbacddcbab"));

    }

    public String longestPalindrome(String s) {
        char[] chars = s.toCharArray();
        int n = chars.length;
        boolean[][] dp = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], true);
        }
        int L = 1,start=0;
        for (int l = 2; l <= n; l++) {          //子串长度
            int j=0;
            for (int i = 0; i < n-l+1; i++) {       //起始位置
                j=i+l-1;
                if (chars[i] == chars[j]&&dp[i+1][j-1]) {
                    L=l;start=i;
                    continue;
                }
                dp[i][j] = false;
            }
        }
        return s.substring(start,start+L);
    }
}
